Natural density

 ( Number Theory ) 

In number theory, natural density, also referred to as asymptotic density or arithmetic density, is a measure of how "large" a subset of the set of is. It relies chiefly on the probability of encountering members of the desired subset when combing through the interval as grows large.

For example, it may seem intuitively that there are more than square number, because every perfect square is already positive and yet many other positive integers exist besides. However, the set of positive integers is not in fact larger than the set of perfect squares: both sets are Infinite set and countable and can therefore be put in bijection. Nevertheless if one goes through the natural numbers, the squares become increasingly scarce. The notion of natural density makes this intuition precise for many, but not all, subsets of the naturals (see Schnirelmann density, which is similar to natural density but defined for all subsets of $\backslash mathbb\{N\}$).

If an integer is randomly selected from the interval , then the probability that it belongs to is the ratio of the number of elements of in to the total number of elements in . If this probability tends to some limit as tends to infinity, then this limit is referred to as the asymptotic density of . This notion can be understood as a kind of probability of choosing a number from the set . Indeed, the asymptotic density (as well as some other types of densities) is studied in probabilistic number theory.

---

Definition A subset of positive integers has natural density if the proportion of elements of among all from to converges to as tends to infinity.

More explicitly, if one defines for any natural number the counting function as the number of elements of less than or equal to , then the natural density of being exactly means that

It follows from the definition that if a set has natural density then .

---

Upper and lower asymptotic density Let $A$ be a subset of the set of natural numbers $\backslash mathbb\{N\}=\backslash \{1,2,\backslash ldots\backslash \}.$ For any $n\; \backslash in\; \backslash mathbb\{N\}$, define $A(n)$ to be the intersection $A(n)=\backslash \{1,2,\backslash ldots,n\backslash \}\; \backslash cap\; A,$ and let $a(n)=|A(n)|$ be the number of elements of $A$ less than or equal to $n$.

Define the upper asymptotic density $\backslash overline\{d\}(A)$ of $A$ (also called the "upper density") by $$\backslash overline\{d\}(A)\; =\; \backslash limsup\_\{n\; \backslash rightarrow\; \backslash infty\}\; \backslash frac\{a(n)\}\{n\}$$ where lim sup is the limit superior.

Similarly, define the lower asymptotic density $\backslash underline\{d\}(A)$ of $A$ (also called the "lower density") by $$\backslash underline\{d\}(A)\; =\; \backslash liminf\_\{n\; \backslash rightarrow\; \backslash infty\}\; \backslash frac\{\; a(n)\; \}\{n\}$$ where lim inf is the limit inferior. One may say $A$ has asymptotic density $d(A)$ if $\backslash underline\{d\}(A)=\backslash overline\{d\}(A)$, in which case $d(A)$ is equal to this common value.

This definition can be restated in the following way: $$d(A)=\backslash lim\_\{n\; \backslash rightarrow\; \backslash infty\}\; \backslash frac\{a(n)\}\{n\}$$ if this limit exists.Nathanson (2000) pp.256–257

These definitions may equivalently be expressed in the following way. Given a subset $A$ of $\backslash mathbb\{N\}$, write it as an increasing sequence indexed by the natural numbers: Then $$\backslash underline\{d\}(A)\; =\; \backslash liminf\_\{n\; \backslash rightarrow\; \backslash infty\}\; \backslash frac\{n\}\{a\_n\},$$ $$\backslash overline\{d\}(A)\; =\; \backslash limsup\_\{n\; \backslash rightarrow\; \backslash infty\}\; \backslash frac\{n\}\{a\_n\}$$ and $$d(A)\; =\; \backslash lim\_\{n\; \backslash rightarrow\; \backslash infty\}\; \backslash frac\{n\}\{a\_n\}$$ if the limit exists.

A somewhat weaker notion of density is the upper Banach density $d^*(A)$ of a set $A\; \backslash subseteq\; \backslash mathbb\{N\}.$ This is defined as $$d^*(A)\; =\; \backslash limsup\_\{N-M\; \backslash rightarrow\; \backslash infty\}\; \backslash frac$$

{N-M+1}.

---

Properties and examples

• For any finite set F of positive integers, d( F) = 0.
• If d( A) exists for some set A and A^c denotes its complement set with respect to $\backslash N$, then d( A^c) = 1 − d( A).
• Corollary: If $F\backslash subset\; \backslash N$ is finite (including the case $F=\backslash emptyset$), $d(\backslash N\; \backslash setminus\; F)=1.$
• If $d(A),\; d(B),$ and $d(A\; \backslash cup\; B)$ exist, then $$$$

\max\{d(A),d(B)\} \leq d(A\cup B) \leq \min\{d(A)+d(B),1\}.

• If $A\; =\; \backslash \{n^2\; :\; n\; \backslash in\; \backslash N\backslash \}$ is the set of all squares, then d( A) = 0.
• If $A\; =\; \backslash \{2n\; :\; n\; \backslash in\; \backslash N\backslash \}$ is the set of all even numbers, then d( A) = 0.5. Similarly, for any arithmetical progression $A\; =\; \backslash \{an\; +\; b\; :\; n\; \backslash in\; \backslash N\backslash \}$ we get $d(A)\; =\; \backslash tfrac\{1\}\{a\}.$
• For the set P of all prime number we get from the prime number theorem that d( P) = 0.
• The set of all square-free integers has density $\backslash tfrac\{6\}\{\backslash pi^2\}.$ More generally, the set of all nth-power-free numbers for any natural n has density $\backslash tfrac\{1\}\{\backslash zeta(n)\},$ where $\backslash zeta(n)$ is the Riemann zeta function.
• The set of has non-zero density.
  (1988). 9780521340564, Cambridge University Press. ISBN 9780521340564
  Marc Deléglise showed in 1998 that the density of the set of abundant numbers is between 0.2474 and 0.2480.
• The set $$A\; =\; \backslash bigcup\_\{n=0\}^\backslash infty\; \backslash left\; \backslash \{2^\{2n\},\backslash ldots,2^\{2n+1\}-1\; \backslash right\; \backslash \}$$ of numbers whose binary expansion contains an odd number of digits is an example of a set which does not have an asymptotic density, since the upper density of this set is $$\backslash overline\; d(A)=\backslash lim\_\{m\; \backslash to\; \backslash infty\}\backslash frac\{1+2^2+\backslash cdots\; +2^\{2m\}\}\{2^\{2m+1\}-1\}=\backslash lim\_\{m\; \backslash to\backslash infty\}\; \backslash frac\{2^\{2m+2\}-1\}\{3(2^\{2m+1\}-1)\}\; =\; \backslash frac\; 23,$$ whereas its lower density is $$\backslash underline\; d(A)=\backslash lim\_\{m\; \backslash to\backslash infty\}\backslash frac\{1+2^2+\backslash cdots\; +2^\{2m\}\}\{2^\{2m+2\}-1\}=\backslash lim\_\{m\; \backslash to\backslash infty\}\; \backslash frac\{2^\{2m+2\}-1\}\{3(2^\{2m+2\}-1)\}\; =\; \backslash frac\; 13.$$
• The set of numbers whose decimal expansion begins with the digit 1 similarly has no natural density: the lower density is 1/9 and the upper density is 5/9.Tenenbaum (1995) p.261 (See Benford's law.)
• Consider an equidistributed sequence $\backslash \{\backslash alpha\_n\backslash \}\_\{n\backslash in\backslash N\}$ in $0,1$ and define a monotone family $\backslash \{A\_x\backslash \}\_\{x\backslash in0,1\}$ of sets:
• If S is a set of positive upper density then Szemerédi's theorem states that S contains arbitrarily large finite arithmetic progressions, and the Furstenberg–Sárközy theorem states that some two members of S differ by a square number.

---

Other density functions Other density functions on subsets of the natural numbers may be defined analogously. For example, the logarithmic density of a set A is defined as the limit (if it exists) $$$$

\mathbf{\delta}(A) = \lim_{x \to \infty} \frac{1}{\log x} \sum_{n \in A, n \le x} \frac{1}{n}.
     

Upper and lower logarithmic densities are defined analogously.

The intuition behind using $\backslash tfrac\{1\}\{n\}$ in the summand comes from the fact that the harmonic series asymptotically approaches $\backslash log\; n\; +\; \backslash gamma$, where $\backslash gamma\; =\; 0.577\backslash ldots$ is the Euler–Mascheroni constant. Thus, this definition ensures that the logarithmic density of the natural numbers is $1$.

For the set of multiples of an integer sequence, the Davenport–Erdős theorem states that the natural density, when it exists, is equal to the logarithmic density.

---

See also

• Dirichlet density
• Erdős conjecture on arithmetic progressions

---

Notes

• Melvyn B. Nathanson (2025). 9780387989129, Springer-Verlag. ISBN 9780387989129

Post Comment